// Source :
// Author : simba
// Date   : 2016-06-08
//任意给定一个32位无符号整数n，求n的二进制表示中1的个数。
//http://www.cnblogs.com/graphics/archive/2010/06/21/1752421.html

package main

import (
	"fmt"
)

//普通法
func BitCount1(n uint) uint {
	var c uint = 0 // 计数器

	for n > 0 {
		if (n & 1) == 1 { // 当前位是1
			c++ // 计数器加1
		}
		n >>= 1 // 移位
	}

	return c
}

//快速法
func BitCount2(n uint) uint {
	var c uint = 0 // 计数器

	for c = 0; n > 0; c++ {
		n &= (n - 1) // 清除最低位的1
	}

	return c
}

func main() {
	//固定测试用例,正确答案 2
	var s1 uint = 5
	a11 := BitCount1(s1)
	a12 := BitCount2(s1)
	fmt.Println("数", s1)
	fmt.Println("输出答案", a11)
	fmt.Println("输出答案", a12)
	fmt.Println("正确答案 2")

	//固定测试用例,正确答案4
	var s3 uint = 15
	a31 := BitCount1(s3)
	a32 := BitCount2(s3)
	fmt.Println("数", s3)
	fmt.Println("输出答案", a31)
	fmt.Println("输出答案", a32)
	fmt.Println("正确答案 4")
}
